#pragma once
#include <assert.h>
// 底层实现 +做题
// 02:22:12    题7. 电话号码字母组合OJ

namespace myvector
{
    template <class T>
    class vector
    {
    public:
        typedef T *iterator;
        typedef const T *const_iterator;

        // 无参默认构造
        vector()
            : _start(nullptr), _finish(nullptr), _endofstorage(nullptr)
        {
        }

        // 析构
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endofstorage = nullptr;
            }
        }

        // 拷贝构造-两种写法
        // 1.
        // vector(const vector<T>& v)
        //{
        //	_start = new T[v.capacity()];
        //	memcpy(_start, v._start, v.size() * sizeof(T));
        //	_finish = _start + v.size();
        //	....
        // }
        // 2.
        // v2(v1);
        vector(const vector<T> &v)
        {
            reserve(v.capacity());  // 先给v2 开和v1同样大的空间
            for (const auto &e : v) // 取v里面的值依次赋值给e，加引用深拷贝，更好
            {
                push_back(e);
            }
        }

        // 赋值运算符重载
        // 传统写法：
        // 1.开空间 2.拷贝数据 3。释放原有空间 4.指向新空间
        vector<T> &operator=(const vector<T> &v)
        {
            if (this != &v)
            {
                T *tmp = new T[v.capacity()];
                for (int i = 0, i < v.size(), i++)
                {
                    tmp[i] = v._start[i];
                    //_start 是一个指向动态分配数组首元素的指针。这个指针类似于数组的首地址，因此可以通过索引访问数组中的元素，就像使用数组一样
                }
                delete[] _start;
                _start = tmp;
                _finish = _start + v.size();
                _endofstorage = _start + v.capacity();
            }
            return *this;
        }
        // 现代写法
        void swap(const vector<T> &v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endofstroage, v._endofstroage);
        }
        vector<T> &operator=(const vector<T> v)
        {
            swap(v);
            return *this;
        }

        // 迭代器区间构造.
        // 构造函数允许你用任何支持迭代器的区间（例如其他容器中的元素）来初始化一个 vector 对象。
        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        ////带参构造
        vector(size_t n, const T &val = T())
        {
            resize(n, val);
        }
        ////带参构造（int）
        vector(int n, const T &val = T())
        {
            resize(n, val);
        }

        // 赋值-现代写法
        // v1=v3;
        void swap(vector<T> &v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endofstorage, v._endofstorage);
        }
        vector<T> &operator=(vector<T> v) // 为什么那里不能用引用，仔细想.02:06:13
        {                                 // 如果用了引用就是 v1和v3交换，而不是v1和v3带来的那个临时变量v 交换
            swap(v);
            return *this;
        }

        // 普通对象的迭代器：提供对容器元素的读写访问。
        // begin
        iterator begin()
        {
            return _start;
        }
        // end
        iterator end()
        {
            return _finish;
        }

        // 常量对象的迭代器：提供对容器元素的只读访问。
        const_iterator begin() const
        {
            return _start;
        }

        const_iterator end() const
        {
            return _finish;
        }

        size_t size() const
        {
            return _finish - _start;
        }

        size_t capacity() const
        {
            return _endofstorage - _start;
        }

        // 这里注意还是要判断n>capacity，因为reserve 也可能单独使用，不能搞成缩容了
        // void reserve
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t old = size(); // 保存当前大小,返回的size()是新的
                T *tmp = new T[n];   // 分配新的内存
                if (_start)          // 复制旧数据到新内存
                {
                    // memcpy(tmp, _start, old * sizeof(T));  memcpy会出问题，是一种浅拷贝test7(),02:03:28
                    for (size_t i = 0; i < old; i++)
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                // 当你重新分配内存时，_finish 和 _endofstorage 的值会基于 size() 和 capacity() 更新
                // 更新指针
                _start = tmp;
                _finish = _start + old; // 将 _finish重新设置为旧大小的位置
                //_finish=_start+size();   错的
                // 删除 old 后，_finish 指针将指向新容量的末尾，而不是当前元素的末尾。这意味着 _finish 会指向一个未初始化的位置，导致对向量的操作（如 push_back）出现未定义行为。
                _endofstorage = _start + n; // 将 _endofstorage 设置为新容量的位置
                                            //_endofstorage=_start+capacity();
            }
        }

        void resize(size_t n, T val = T())

        { // 三种情况假设有5个数据，容量为10.则有resize(3),resize(7),resize(14)三种情况
            if (n > size())
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
            else
            {
                _finish = _start + n;
            }
        }
        // 为什么缺省参数能这样写？
        // 兼容模板
        //	在模板类中，成员函数需要适应各种类型的参数。默认构造函数 T() 适用于大多数类型，因此能够确保 resize 函数可以正确处理不同类型的对象。例如：
        //	对于基本类型（如 int），T() 将初始化为 0。
        //	对于自定义类型，如果提供了默认构造函数，T() 将调用该构造函数。
        //	对于指针类型，T() 将初始化为 nullptr。
        // 缺省参数的灵活性
        //	缺省参数 val = T() 允许用户在调用 resize 函数时选择性地提供填充值。如果用户没有提供，resize 函数将使用 T() 作为默认值，这样可以简化函数调用，并使代码更具通用性。
        //

        void push_back(const T &x)
        {
            if (_finish == _endofstorage)
            {
                size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
                // 如果 capacity() == 0,则让 capacity()=4，
                // 如果 capacity() !=0 ,则让 capacity()=capacity()*2
                reserve(newcapacity);
            }
            *_finish = x;
            ++_finish;
        }

        void pop_back()
        {
            assert(size() > 0);
            --_finish;
        }

        // vector 不支持头插  头删

        // pos位置之前插入x

        // 下面这个代码多次运行会失效，原因：迭代器失效。 pos扩容后失效，及时更新即可。
        //
        // void insert(iterator pos, const T& x)
        //{
        //	assert(pos >= _start && pos <= _finish); // 确保插入位置合法
        //	if (_finish == _endofstorage) // 如果存储空间已满
        //	{
        //		reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩充存储空间
        //	}
        //	iterator end = _finish - 1; // 初始化end为最后一个元素的位置
        //	while (end >= pos) // 从后向前移动元素，直到插入位置
        //	{
        //		*(end + 1) = *end; // 将元素向后移动一位
        //		end--; // 继续向前移动
        //	}
        //	*pos = x; // 在插入位置插入新元素
        //	++_finish; // 更新_finish指针
        // }

        /* 插入 */
        // void insert(iterator pos, const T& x) {
        //	assert(pos >= _start);
        //	assert(pos <= _finish);

        //	// 检查是否需要增容
        //	if (_finish == _endofstorage) {
        //		// 扩容会导致迭代器失效，扩容需要更新一下 pos
        //		size_t len = pos - _start;
        //		reserve(capacity() == 0 ? 4 : capacity() * 2);

        //		pos = _start + len;
        //	}

        //	// 移动数据
        //	iterator end = _finish - 1;
        //	while (end >= pos) {
        //		*(end + 1) = *end;
        //		end--;
        //	}

        //	// 插入数据
        //	*pos = x;
        //	_finish++;
        //}

        // 解决：
        /* 插入 */
        iterator insert(iterator pos, const T &x)
        {
            assert(pos >= _start);
            assert(pos <= _finish);

            // 检查是否需要增容
            if (_finish == _endofstorage)
            {
                // 扩容会导致迭代器失效，扩容需要更新一下 pos
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);

                pos = _start + len;
            }

            // 移动数据
            iterator end = _finish - 1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                end--;
            }

            // 插入数据
            *pos = x;
            _finish++;
            return pos;
        }

        // 注意是 从pos起始位置往后的所有数据，挪到pos+1上
        // memmove(pos + 1, pos, sizeof(T) * (_finish - pos));

        // 删除pos位置数据
        // void erase(iterator pos)
        //{
        //	assert(pos >= _start && pos < _finish);
        //	memmove(pos, pos + 1, sizeof(T) * (_finish - pos));
        //	--_finish;
        // }

        // void erase(iterator pos)
        //{
        //	assert(pos <= _finish);
        //	assert(pos >= _start);
        //	iterator begin = pos + 1;
        //	while (begin < _finish)
        //	{
        //		*(begin - 1) = *begin;
        //		begin++;
        //	}
        //	_finish--;
        // }

        iterator erase(iterator pos)
        {
            assert(pos >= _start && pos < _finish);
            iterator it = pos + 1;
            while (it < _finish)
            {
                *(it - 1) = *it;
                ++it;
            }
            _finish--;
            return pos;
        }

        //[]访问
        // 返回可修改的引用，支持读写操作
        T &operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }
        // 支持读取操作但不能修改。
        const T &operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
        // 返回类型为T&有以下几个原因：
        // 方便读写操作
        //

    private:
        iterator _start = nullptr;        // 这个成员变量指向动态数组中第一个实际存储元素的内存位置。[
        iterator _finish = nullptr;       // 指向当前已填充元素的末尾，即最后一个有效元素的下一个位置。)
        iterator _endofstorage = nullptr; // 指向动态数组的末尾，即分配的内存块的最后一个位置。
        // 1    2    3     4     空    空
        // ↑_start				↑	   ↑：_endofstorage
        //					_finish
    };

    void print_vector(const vector<int> &v)
    {
        // 此处为什么不能用范围for？
        // 因为const vector<int>& v 是const，迭代器也要用const的，所以要有const的begin和end
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    void test_vecotr1()
    {
        // 插入几个数据测试
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);

        // 迭代器打印
        vector<int>::iterator it = v.begin(); // 一定要写清楚iterator是哪个容器的迭代器 vector<int>::
        while (it != v.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        // 范围for打印
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        //[]+下标
        for (size_t i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
        }
        cout << endl;

        // v[0]++;

        // 测试
        vector<int> v2;
        v2.push_back(11);
        v2.push_back(22);
        v2.push_back(33);
        v2.push_back(44);
        v2.push_back(55);
        v2.push_back(66);
        vector<int>::iterator it2 = v2.begin(); // 一定要写清楚iterator是哪个容器的迭代器 vector<int>::
        while (it2 != v2.end())
        {
            cout << *it2 << " ";
            ++it2;
        }
        cout << endl;

        v = v2;
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        ////resize 如何给缺省值呢？	T  val=T()
        ////c++对内置类型进行了一个升级
        // int i = 0;
        // int j = int();
        // int k = int(10);

        // vector<int >v1 = v;  //是拷贝构造。两个对象都存在了才叫赋值
    }
    void test_vector3()
    {
        vector<double> v;
        v.reserve(10);
        v.push_back(1.1);
        v.push_back(2.2);
        v.push_back(3.3);
        v.push_back(4.4);
        v.push_back(5.5);
        v.push_back(6.6);
        v.resize(3);
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;

        // v.resize(8);
        // for (auto e : v)
        //{
        //	cout << e << " ";
        // }
        // cout << endl;

        // v.resize(18);
        // for (auto e : v)
        //{
        //	cout << e << " ";
        // }
        // cout << endl;
        v.erase(v.begin() + 2); // 获取一个指向第三个元素的迭代器.不能用整数索引
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 迭代器失效：
    // 1.insert 扩容的时候的pos. 以及外部迭代器失效:v.insert(it,20) pos是it的拷贝，不会影响it，也可能会失效
    // 2.erase 的形参pos
    //!!!原则是 insert和erase过的迭代器不要使用。
    // 失效其实有两种，一种是野指针，一种是没有指向原来的位置。

    // 问题代码：
    // void test_vector4()
    //{
    //	vector <int> v;
    //	v.push_back(1);
    //	v.push_back(2);
    //	v.push_back(3);
    //	v.push_back(4);

    //	for (auto e : v)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;
    //	vector<int>::iterator it = v.begin();
    //	while (it != v.end())
    //	{
    //		if (*it % 2 == 0)
    //		{
    //			v.erase(it);
    //		}
    //		++it;
    //	}
    //	for (auto e : v)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;
    //}
    // 当调用 erase 函数删除元素时，原来的迭代器 it 变得无效，再次使用它会导致未定义行为。
    // 调用 erase 后，所有指向被删除元素之后的迭代器都将失效。在当前情况下，it 变得无效，因为它指向的位置已经被删除。
    // 删除元素后，代码继续执行 ++it，这将导致对无效迭代器的递增操作，从而引发未定义行为和崩溃。

    // 改进：
    // void test_vector5()
    //{
    //	vector<int> v;
    //	v.push_back(1);
    //	v.push_back(2);
    //	v.push_back(3);
    //	v.push_back(4);

    //	for (auto e : v)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;

    //	vector<int>::iterator it = v.begin();
    //	while (it != v.end())
    //	{
    //		if (*it % 2 == 0)
    //		{
    //			it = v.erase(it);  // 更新迭代器
    //		}
    //		else
    //		{
    //			++it;  // 仅当没有删除时才递增迭代器
    //		}
    //	}

    //	for (auto e : v)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;
    //}

    void test_vector6()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
        v.erase(v.begin() + 3);
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 拷贝数据用memcpy出现问题
    // void test_vector7()
    //{
    //	vector<int> v;
    //	v.push_back(1);
    //	v.push_back(2);
    //	v.push_back(3);
    //	v.push_back(4);
    //	v.push_back(5);
    //	v.push_back(6);
    //	v.push_back(7);
    //	v.push_back(8);
    //	v.push_back(9);
    //	for (auto e : v)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;

    //	vector<string> vstr;
    //	vstr.push_back("1111");
    //	vstr.push_back("1111");
    //	vstr.push_back("1111");
    //	vstr.push_back("1111");
    //	vstr.push_back("1111");

    //	for (auto e : vstr)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;
    //}

    // 迭代器区间构造的使用
    // void testvector8()
    //{
    //	vector<int> v1;
    //	v1.push_back(1);
    //	v1.push_back(2);
    //	v1.push_back(3);
    //	v1.push_back(4);
    //	v1.push_back(5);

    //	vector<int> v2(v1.begin(), v1.end());
    //	for (auto e : v2)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;

    //	list<int> lt;
    //	lt.push_back(10);
    //	lt.push_back(20);
    //	lt.push_back(30);
    //	lt.push_back(40);
    //	vector<int> v3(lt.begin(), lt.end());
    //	for (auto e : v3)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;

    //	int a[] = { 100, 200, 300 };
    //	vector<int> v4(a, a+3);
    //	for (auto e : v4)
    //	{
    //		cout << e << " ";
    //	}
    //	cout << endl;

    //}

    void test_vector9()
    {
        vector<string> v1(5, "1111");
        for (auto e : v1)
        {
            cout << e << " ";
        }
        cout << endl;

        // 下面这个也运行的时候报错：非法的间接寻址

        // 图片板书里有解释原因，再加一个int版本的就行了
        vector<int> v2(5, 1);
        for (auto e : v2)
        {
            cout << e << " ";
        }
        cout << endl;
    }

    // 以下为我自己写博客的测试
    void test_vector10()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(4);
        v.push_back(5);
        vector<int>::iterator it = v.begin();
        // 删除所有偶数
        while (it != v.end())
        {
            if (*it % 2 == 0)
            {
                v.erase(it);
            }
            ++it;
        }
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}
